#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define re register
#define N 445000
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int mo=998244353;
struct que{
int x,y,i;
}p[N];
inline int read(){
int x=0,w=0;char ch=getchar();
while (!isdigit(ch))w|=ch=='-',ch=getchar();
while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return w?-x:x;
}
int a[N],c[N],n,m,d[N],ans[N],w[N];
vector<int>v[N];
void add1(int x,int d){
for (;x;x&=(x-1))c[x]+=d;
}
int q1(int x){
int res=0;
for (;x<=n;x+=(x&(-x)))res+=c[x];
return res;
}
void add(int x,int d){
for (;x<=n;x+=(x&(-x)))w[x]+=d;
}
int q(int x){
int res=0;
for (;x;x&=(x-1))res+=w[x];
return res;
}
bool cmp(que a,que b){
return a.x<b.x;
}
signed main(){
n=read(),m=read();
for (int i=1;i<=n;++i){
a[i]=read();
// if (i-a[i]>=0)v[i-a[i]].push_back(i);
}
for (int i=1;i<=n;++i){
int l=1,r=i;
while (l<=r){
int mid=(l+r)>>1;
if (q1(mid)>=i-a[i])l=mid+1,d[i]=mid;
else r=mid-1;
}
if (i-a[i]>=0&&d[i])add1(d[i],1),v[d[i]].push_back(i),add(i,1);
// cout<<i<<" "<<i-a[i]<<" "<<d[i]<<"!"<<endl;
}
memset(c,0,sizeof(c));
for (int i=1;i<=m;++i)p[i].x=read()+1,p[i].y=n-read(),p[i].i=i;
sort(p+1,p+1+m,cmp);
for (int i=1,j=1;i<=n;++i){
for (;j<=m&&p[j].x==i;++j){
ans[p[j].i]=q(p[j].y)-q(p[j].x-1);
}
for (int k=0;k<v[i].size();++k)
add(v[i][k],-1);
}
for (int i=1;i<=m;++i)printf("%d\n",ans[i]);
return 0;
}
733. Flood Fill | 206. Reverse Linked List |
83. Remove Duplicates from Sorted List | 116. Populating Next Right Pointers in Each Node |
145. Binary Tree Postorder Traversal | 94. Binary Tree Inorder Traversal |
101. Symmetric Tree | 77. Combinations |
46. Permutations | 226. Invert Binary Tree |
112. Path Sum | 1556A - A Variety of Operations |
136. Single Number | 169. Majority Element |
119. Pascal's Triangle II | 409. Longest Palindrome |
1574A - Regular Bracket Sequences | 1574B - Combinatorics Homework |
1567A - Domino Disaster | 1593A - Elections |
1607A - Linear Keyboard | EQUALCOIN Equal Coins |
XOREQN Xor Equation | MAKEPAL Weird Palindrome Making |
HILLSEQ Hill Sequence | MAXBRIDGE Maximise the bridges |
WLDRPL Wildcard Replacement | 1221. Split a String in Balanced Strings |
1002. Find Common Characters | 1602A - Two Subsequences |